package com.sx.sx1.lintcode.day717;

import java.util.HashMap;
import java.util.Map;

public class LC313 {

    static class Solution {
        /**
         * @param a: the array you need to operate.
         * @param b: the target array.
         * @return: return the minimum number of operations.
         */
        public int minimumInsertion(int[] a, int[] b) {
       /*
            解题思路
            我们先简化问题，每次需要将第一个或最后一个元素插入到数组，最后使数组有序，应该怎么计算。
            其实我们是要将一段前缀和一段后缀插入到剩下的一部分中，其实就是要保留一段递增的中缀，
            那么题目就变成了求最长递增子串的问题，最终的结果就是数组长度减去最长递增子串的长度。
            a的长度  - a和b的最长公共子序列的长度
             */
            int n = a.length;
            //记录每个数在b中的权重信息
            Map<Integer,Integer> pos = new HashMap<>();
            for (int i = 0; i <n ; i++) {
                pos.put(b[i],i);
            }

            //根据b中的每个数的权重信息，得到a中最长的递增子序列
            int ans = 1;
            int t=1;
            for (int i = 1; i < n; i++) {
                if(pos.get(a[i]) > pos.get(a[i-1])){
                    t++;
                    ans=Math.max(ans,t);
                }else{
                    t=1;
                }
            }
            return n-ans;

        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.minimumInsertion(new int[]{5,4,1,3,2},new int[]{1,2,3,4,5}));
    }
}


/*
LintCode-Logo
学习
刷题
内推
VIP
其他...
搜索题目、标签、题集
邀请有礼
中文
您上个月的个人报告已生成，点击查看
avatar
313 · 最小插入次数
算法
困难
通过率
52%

题目
题解2
笔记
讨论6
排名
记录
描述
有两个数组 aa 和 bb，两个数组都由相同的整型数字集合组成，且每个数组中无重复。
每次操作可以将 aa 的第一个或最后一个数字插入到 aa 的任何位置中。
问最少操作几次，可以将 aa 变换成 bb。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


两个数组的长度均为 nn，1 \le n \le 10^51≤n≤10
5
 。
数组中的每个元素满足 1 \le a_i, b_i \le 10^91≤a
i
​
 ,b
i
​
 ≤10
9
 。
在样例中，aa 的操作步骤如下：

将 22 插入到 1, 31,3 中间，得到 [5,4,1,2,3][5,4,1,2,3]。
将 55 放到最后，得到 [4,1,2,3,5][4,1,2,3,5]。
将 44 插入到 3, 53,5 中间，得到 [1,2,3,4,5][1,2,3,4,5]。
样例
样例输入：
a = [5,4,1,3,2]
b = [1,2,3,4,5]
样例输出：
3
标签
推荐课程

系统设计 System Design 2024版
数据库、API、GFS、视频流等16大系统设计详解，实战练习拿下面试/晋升“拦路虎”
308/3325
已开启智能提示
发起考试
45 分 00 秒
12345678910

控制台
        历史提交

 */
